//单调栈
class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        int ans=0;
        stack<int> st;
        for(int i=0; i<n; i++)
        {
            int uh=height[i];
            while(!st.empty()&&height[st.top()]<=uh)
            {
                int bottomh=height[st.top()]; st.pop();
                if(st.empty()) break;
                int left=st.top();
                int square=min(height[left], height[i])-bottomh; //可放水的面积
                ans+=square*(i-left-1);
            }
            st.push(i);
        }
        return ans;
    }
};